package solver

import (
	"gosudoku/set"
	"log"
	"slices"
)

func (g *Grid) UniqueRectangle(handler func(int, []int, int) bool) (used bool) {
	for i, row := range g.rows {
		pairs := getURPairs(row)
		for _, pair := range pairs {
			for j := range g.rows {
				if i == j {
					continue
				}
				if !sameBoxes([]int{i, j}, pair) {
					continue
				}
				if !g.verifyRectangle(i, pair, j) {
					continue
				}
				if handler(i, pair, j) {
					used = true
					return
				}
			}
		}
	}
	return
}

func sameBoxes(rowNums, colNums []int) bool {
	return (rowNums[0]/3 == rowNums[1]/3 && colNums[0]/3 != colNums[1]/3) ||
		(rowNums[0]/3 != rowNums[1]/3 && colNums[0]/3 == colNums[1]/3)
}

func getURPairs(row House) (pairs [][]int) {
	for i, cell0 := range row.cells {
		for j, cell1 := range row.cells[i+1:] {
			if cell0.cands.Intersect(cell1.cands).Count() != 2 {
				continue
			}
			if cell0.cands.Count() == 2 {
				pairs = append(pairs, []int{i, j + i + 1})
			} else if cell1.cands.Count() == 2 {
				pairs = append(pairs, []int{j + i + 1, i})
			}
		}
	}
	return
}

func (g *Grid) verifyRectangle(rowNum1 int, pair []int, rowNum2 int) bool {
	cands := g.rows[rowNum1].cells[pair[0]].cands

	cell2 := g.rows[rowNum2].cells[pair[0]]
	cell3 := g.rows[rowNum2].cells[pair[1]]

	if rowNum1 < rowNum2 && cell2.cands.Count() == 2 { //has been verified
		return false
	}

	if cands.Intersect(cell2.cands) != cands {
		return false
	}

	if cands.Intersect(cell3.cands) != cands {
		return false
	}
	return true
}

func (g *Grid) handleURType1(rowNum1 int, pair []int, rowNum2 int) (used bool) {
	cells := make([]*Cell, 4)
	cells[0] = g.rows[rowNum1].cells[pair[0]]
	cells[1] = g.rows[rowNum1].cells[pair[1]]
	cells[2] = g.rows[rowNum2].cells[pair[0]]
	cells[3] = g.rows[rowNum2].cells[pair[1]]

	count := 0
	cands := cells[0].cands
	var zCell *Cell
	for _, cell := range cells[1:] {
		if cands != cell.cands {
			count++
			zCell = cell
		}
	}
	if count != 1 {
		return
	}
	if zCell.removeCands(cands.GetList()) {
		log.Printf("r%v%vc%v%v %v Unique Rectangle Type1",
			rowNum1, rowNum2, pair[0], pair[1], cands.ValueString())
		return true
	}

	return
}
func (g *Grid) UniqueRectangleType1() (used bool) {
	used = g.UniqueRectangle(g.handleURType1)
	return
}

func (g *Grid) handleURType2A(rowNum1 int, pair []int, rowNum2 int) (used bool) {
	cells := make([]*Cell, 4)
	cells[0] = g.rows[rowNum1].cells[pair[0]]
	cells[1] = g.rows[rowNum1].cells[pair[1]]
	cells[2] = g.rows[rowNum2].cells[pair[0]]
	cells[3] = g.rows[rowNum2].cells[pair[1]]

	cands := cells[0].cands

	zCells := make([]*Cell, 0, 2)
	if cells[1].cands == cands {
		zCells = append(zCells, cells[2])
		zCells = append(zCells, cells[3])
	}
	if cells[2].cands == cands {
		zCells = append(zCells, cells[1])
		zCells = append(zCells, cells[3])
	}

	if len(zCells) != 2 {
		return
	}

	if zCells[0].cands.Count() != 3 || zCells[0].cands != zCells[1].cands {
		return
	}

	cand := zCells[0].cands.Diff(cands).GetList()[0]
	if g.clearupSeenCand(cand, zCells) {
		log.Printf("r%v%vc%v%v %v Unique Rectangle Type2A",
			rowNum1, rowNum2, pair[0], pair[1], cands.ValueString())
		return true
	}

	return
}

func (g *Grid) clearupSeenCands(cands []int, cells []*Cell) (used bool) {
	shares := g.seenCells(cells[0])
	for _, cell := range cells[1:] {
		shares = shareCells(shares, g.seenCells(cell))
	}

	for _, cell := range shares {
		if cell.removeCands(cands) {
			used = true
		}
	}

	return
}

func (g *Grid) clearupSeenCand(cand int, cells []*Cell) (used bool) {
	return g.clearupSeenCands([]int{cand}, cells)
}

func (g *Grid) UniqueRectangleType2A() (used bool) {
	used = g.UniqueRectangle(g.handleURType2A)
	return
}

func (g *Grid) handleURType2B(rowNum1 int, pair []int, rowNum2 int) (used bool) {
	cells := make([]*Cell, 4)
	cells[0] = g.rows[rowNum1].cells[pair[0]]
	cells[1] = g.rows[rowNum1].cells[pair[1]]
	cells[2] = g.rows[rowNum2].cells[pair[0]]
	cells[3] = g.rows[rowNum2].cells[pair[1]]

	cands := cells[0].cands

	if cells[1].cands.Count() != 3 || cells[1].cands != cells[2].cands {
		return
	}

	if cells[3].cands != cands && cells[3].cands != cells[1].cands {
		return
	}

	zCells := make([]*Cell, 0)

	zCells = append(zCells, cells[1])
	zCells = append(zCells, cells[2])

	if cells[1].cands != cells[3].cands {
		zCells = append(zCells, cells[3])
	}

	cand := zCells[0].cands.Diff(cands).GetList()[0]
	if g.clearupSeenCand(cand, zCells) {
		log.Printf("r%v%vc%v%v %v Unique Rectangle Type2B",
			rowNum1, rowNum2, pair[0], pair[1], cands.ValueString())
		return true
	}

	return
}

func (g *Grid) UniqueRectangleType2B() (used bool) {
	used = g.UniqueRectangle(g.handleURType2B)
	return
}

func (g *Grid) UniqueRectangleType3A() (used bool) {
	used = g.UniqueRectangle(g.handleURType3A)
	return
}

func (g *Grid) UniqueRectangleType3B() (used bool) {
	used = g.UniqueRectangle(g.handleURType3B)
	return
}

func (g *Grid) handleURType3B(rowNum1 int, pair []int, rowNum2 int) (used bool) {
	return g.handleURType3(rowNum1, pair, rowNum2, false)
}

func (g *Grid) handleURType3A(rowNum1 int, pair []int, rowNum2 int) (used bool) {
	return g.handleURType3(rowNum1, pair, rowNum2, true)
}

func (g *Grid) handleURType3(rowNum1 int, pair []int, rowNum2 int, nake bool) (used bool) {
	cells := make([]*Cell, 4)
	cells[0] = g.rows[rowNum1].cells[pair[0]]
	cells[1] = g.rows[rowNum1].cells[pair[1]]
	cells[2] = g.rows[rowNum2].cells[pair[0]]
	cells[3] = g.rows[rowNum2].cells[pair[1]]

	cands := cells[0].cands

	zCells := make([]*Cell, 0, 2)
	if cells[1].cands == cands {
		zCells = append(zCells, cells[2])
		zCells = append(zCells, cells[3])
	}
	if cells[2].cands == cands {
		zCells = append(zCells, cells[1])
		zCells = append(zCells, cells[3])
	}

	if len(zCells) != 2 {
		return
	}

	line := g.rows[zCells[0].rowNum]
	cellNums := []int{zCells[0].colNum, zCells[1].colNum}
	if zCells[0].colNum == zCells[1].colNum {
		line = g.cols[zCells[0].colNum]
		cellNums = []int{zCells[0].rowNum, zCells[1].rowNum}
	}

	if g.handleURType3House(cands, line, cellNums, nake) {
		used = true
	}
	if zCells[0].boxNum == zCells[1].boxNum {
		box := g.boxes[zCells[0].boxNum]
		cellNums = []int{zCells[0].cellNum, zCells[1].cellNum}
		if g.handleURType3House(cands, box, cellNums, nake) {
			used = true
		}
	}

	if used {
		sname := "Unique Rectangle Type3B"
		if nake {
			sname = "Unique Rectangle Type3A"
		}
		log.Printf("r%v%vc%v%v %v %s",
			rowNum1, rowNum2, pair[0], pair[1], cands.ValueString(), sname)
	}

	return
}

func (g *Grid) handleURType3House(cands set.Set, house House, pair []int, nake bool) (used bool) {
	unsolvedCellNums := []int{}
	for cellNum, cell := range house.cells {
		if slices.Contains(pair, cellNum) || cell.solved() {
			continue
		}
		unsolvedCellNums = append(unsolvedCellNums, cellNum)
	}
	remainCands := house.cells[pair[0]].cands.Union(
		house.cells[pair[1]].cands).Diff(cands)

	var ok bool
	var subset []int
	var removeCands []int
	for i := 1; i <= 3; i++ {
		//ok, subset, remainCands =
		//fmt.Println(house.kind, unsolvedCellNums, pair, "!!!!!remainCands", remainCands)
		if nake {
			ok, subset, removeCands = verifyURType3NakedSubSet(i, house, remainCands, unsolvedCellNums)
		} else {
			ok, subset, removeCands = verifyURType3HiddenSubSet(i, house, cands,
				remainCands, unsolvedCellNums)
		}

		if !ok {
			continue
		}
		for _, cellNum := range subset {
			if house.cells[cellNum].removeCands(removeCands) {
				used = true
			}
		}
		return
	}
	return
}

func verifyURType3NakedSubSet(cellCount int, house House, remainCands set.Set,
	unsolvedCellNums []int) (ok bool, removeCellNums, removeCands []int) {
	if cellCount > len(unsolvedCellNums)/2 {
		return
	}

	for _, subset := range combine(unsolvedCellNums, cellCount) {
		subsetCands := remainCands
		for _, cellNum := range subset {
			subsetCands = subsetCands.Union(house.cells[cellNum].cands)
		}
		if subsetCands.Count() != cellCount+1 {
			continue
		}
		ok = true
		removeCellNums = set.NewSet(unsolvedCellNums).Diff(
			set.NewSet(subset)).GetList()
		removeCands = subsetCands.GetList()
		return
	}
	return
}

func verifyURType3HiddenSubSet(cellCount int, house House, uRCands,
	remainCands set.Set, unsolvedCellNums []int) (
	ok bool, removeCellNums, removeCands []int) {
	if cellCount > len(unsolvedCellNums)/2 {
		return
	}

	//fmt.Println(unsolvedCellNums, cellCount, house.kind)

	for _, subset := range combine(unsolvedCellNums, cellCount) {
		hiddenCands := uRCands
		for _, cellNum := range subset {
			hiddenCands = hiddenCands.Union(house.cells[cellNum].cands)
		}
		for _, cellNum := range set.NewSet(unsolvedCellNums).Diff(set.NewSet(subset)).GetList() {
			hiddenCands = hiddenCands.Diff(house.cells[cellNum].cands)
		}

		hiddenCands = hiddenCands.Diff(remainCands)

		if hiddenCands.Count() != cellCount+1 {
			continue
		}

		ok = true
		removeCellNums = subset
		removeCands = set.NewFull().Diff(hiddenCands).GetList()
		return
	}
	return
}

func (g *Grid) handleURType4A(rowNum1 int, pair []int, rowNum2 int) (used bool) {
	cells := make([]*Cell, 4)
	cells[0] = g.rows[rowNum1].cells[pair[0]]
	cells[1] = g.rows[rowNum1].cells[pair[1]]
	cells[2] = g.rows[rowNum2].cells[pair[0]]
	cells[3] = g.rows[rowNum2].cells[pair[1]]

	cands := cells[0].cands

	zCells := make([]*Cell, 0)
	if cells[1].cands == cands {
		zCells = append(zCells, cells[2])
		zCells = append(zCells, cells[3])
	} else if cells[2].cands == cands {
		zCells = append(zCells, cells[1])
		zCells = append(zCells, cells[3])
	} else {
		return
	}
	line := g.rows[rowNum2]
	if zCells[0].colNum == zCells[1].colNum {
		line = g.cols[zCells[0].colNum]
	}

	scands := cands.GetList()
	removeCand := -1
	for i, cand := range scands {
		if isOnlyTwoCand(cand, line, pair) {
			removeCand = scands[1-i]
		}
	}
	if removeCand == -1 {
		return
	}

	for _, cell := range zCells {
		cell.removeCand(removeCand)
	}

	log.Printf("r%v%vc%v%v %v Unique Rectangle Type4A",
		rowNum1, rowNum2, pair[0], pair[1], cands.ValueString())

	return true
}

func isOnlyTwoCand(cand int, line House, butCellNums []int) bool {
	for cellNum, cell := range line.cells {
		if cell.solved() || slices.Contains(butCellNums, cellNum) {
			continue
		}
		if cell.cands.Has(cand) {
			return false
		}
	}
	return true
}

func (g *Grid) UniqueRectangleType4A() (used bool) {
	used = g.UniqueRectangle(g.handleURType4A)
	return
}

func (g *Grid) handleURType4B(rowNum1 int, pair []int, rowNum2 int) (used bool) {
	cells := make([]*Cell, 4)
	cells[0] = g.rows[rowNum1].cells[pair[0]]
	cells[1] = g.rows[rowNum1].cells[pair[1]]
	cells[2] = g.rows[rowNum2].cells[pair[0]]
	cells[3] = g.rows[rowNum2].cells[pair[1]]

	cands := cells[0].cands

	if cells[3].cands != cands {
		return
	}
	rows := []House{g.rows[rowNum1], g.rows[rowNum2]}
	cols := []House{g.cols[pair[0]], g.cols[pair[1]]}
	removeCand := -1
	rowNums := []int{rowNum1, rowNum2}
	for _, cand := range cands.GetList() {
		if isOnlyTwoCand(cand, rows[0], pair) && isOnlyTwoCand(cand, rows[1], pair) &&
			isOnlyTwoCand(cand, cols[0], rowNums) && isOnlyTwoCand(cand, cols[1], rowNums) {
			removeCand = cand
			break
		}
	}
	if removeCand == -1 {
		return
	}

	cells[1].removeCand(removeCand)
	cells[2].removeCand(removeCand)

	log.Printf("r%v%vc%v%v %v Unique Rectangle Type4B",
		rowNum1, rowNum2, pair[0], pair[1], cands.ValueString())

	return true
}

func (g *Grid) UniqueRectangleType4B() (used bool) {
	used = g.UniqueRectangle(g.handleURType4B)
	return
}

func (g *Grid) handleURType4C(rowNum1 int, pair []int, rowNum2 int) (used bool) {
	cells := make([]*Cell, 4)
	cells[0] = g.rows[rowNum1].cells[pair[0]]
	//cells[1] = g.rows[rowNum1].cells[pair[1]]
	//cells[2] = g.rows[rowNum2].cells[pair[0]]
	cells[3] = g.rows[rowNum2].cells[pair[1]]

	cands := cells[0].cands

	row := g.rows[rowNum2]
	col := g.cols[pair[1]]
	removeCand := -1
	scands := cands.GetList()

	rowNums := []int{rowNum1, rowNum2}
	for i, cand := range scands {
		if isOnlyTwoCand(cand, row, pair) &&
			isOnlyTwoCand(cand, col, rowNums) {
			removeCand = scands[1-i]
			break
		}
	}
	if removeCand == -1 {
		return
	}

	cells[3].removeCand(removeCand)

	log.Printf("r%v%vc%v%v %v Unique Rectangle Type4C",
		rowNum1, rowNum2, pair[0], pair[1], cands.ValueString())

	return true
}

func (g *Grid) UniqueRectangleType4C() (used bool) {
	used = g.UniqueRectangle(g.handleURType4C)
	return
}

func (g *Grid) handleURXYZWing(rowNum1 int, pair []int, rowNum2 int) (used bool) {
	cells := make([]*Cell, 4)
	cells[0] = g.rows[rowNum1].cells[pair[0]]
	cells[1] = g.rows[rowNum1].cells[pair[1]]
	cells[2] = g.rows[rowNum2].cells[pair[0]]
	cells[3] = g.rows[rowNum2].cells[pair[1]]

	cands := cells[0].cands

	pCells := make([]*Cell, 0, 2)
	if cells[1].cands == cands {
		pCells = append(pCells, cells[2])
		pCells = append(pCells, cells[3])
	}
	if cells[2].cands == cands {
		pCells = append(pCells, cells[1])
		pCells = append(pCells, cells[3])
	} else {
		return
	}

	pivotCands := pCells[0].cands.Union(pCells[1].cands).Diff(cands)
	if pivotCands.Count() != 2 && pivotCands.Count() != 3 {
		return
	}
	ok, z, wings := g.verifyURXYZWing(pivotCands, pCells)
	if !ok {
		return
	}
	sname := "Unique Rectangle XY-Wing"
	if pivotCands.Has(z) {
		sname = "Unique Rectangle XYZ-Wing"
	}
	if g.clearupURXYZWing(cands, z, pCells, wings) {
		used = true
		log.Printf("r%v%vc%v%v %v wr%vc%v wr%vc%v %v %v",
			rowNum1, rowNum2, pair[0], pair[1], cands.ValueString(),
			wings[0].rowNum, wings[0].colNum, wings[1].rowNum, wings[1].colNum,
			toValue(z), sname)
	}
	return
}

func (g *Grid) clearupURXYZWing(cands set.Set, z int, pCells, wings []*Cell) (used bool) {
	for i, wing := range wings {
		if wing.cands.Has(z) {
			wings[0], wings[i] = wings[i], wings[0]
			break
		}
	}

	cells := g.seenCells(wings[0])
	for _, wing := range wings[1:] {
		if wing.cands.Has(z) {
			cells = shareCells(cells, g.seenCells(wing))
		}
	}

	for _, pivot := range pCells {
		if pivot.cands.Diff(cands).Has(z) {
			cells = shareCells(cells, g.seenCells(pivot))
		}
	}

	for _, cell := range cells {
		if cell.removeCand(z) {
			used = true
		}
	}
	return
}

func (g *Grid) verifyURXYZWing(pivotCands set.Set, pCells []*Cell) (ok bool, cand int, wings []*Cell) {
	xzWings := g.seenCells(pCells[0])
	xzWings = filterBiCands(xzWings, 2)
	xzWings = filterCells(xzWings, pCells[1])

	yzWings := g.seenCells(pCells[1])
	yzWings = filterBiCands(yzWings, 2)
	yzWings = filterCells(yzWings, pCells[0])

	for _, xzWing := range xzWings {
		for _, yzWing := range yzWings {
			wingCands := xzWing.cands.Union(yzWing.cands)
			zCands := xzWing.cands.Intersect(yzWing.cands)
			if wingCands.Count() != 3 || zCands.Count() != 1 {
				continue
			}
			if wingCands.Intersect(pivotCands) != pivotCands {
				continue
			}

			x := xzWing.cands.Diff(zCands).GetList()[0]
			if pCells[0].cands.Has(x) && !sameHouse([]*Cell{xzWing, pCells[0]}) {
				continue
			}
			if pCells[1].cands.Has(x) && !sameHouse([]*Cell{xzWing, pCells[1]}) {
				continue
			}
			y := yzWing.cands.Diff(zCands).GetList()[0]
			if pCells[0].cands.Has(y) && !sameHouse([]*Cell{yzWing, pCells[0]}) {
				continue
			}
			if pCells[1].cands.Has(y) && !sameHouse([]*Cell{yzWing, pCells[1]}) {
				continue
			}
			ok = true
			cand = zCands.GetList()[0]
			wings = []*Cell{xzWing, yzWing}
			return
		}
	}
	return

}

func (g *Grid) UniqueRectangleXYZWing() (used bool) {
	used = g.UniqueRectangle(g.handleURXYZWing)
	return
}

func filterBiCands(cells []*Cell, max int) []*Cell {
	fs := []*Cell{}
	for _, cell := range cells {
		if cell.cands.Count() >= 2 && cell.cands.Count() <= max {
			fs = append(fs, cell)
		}
	}
	return fs
}

func filterCells(cells []*Cell, filterCell *Cell) []*Cell {
	fs := []*Cell{}
	for _, cell := range cells {
		if cell != filterCell {
			fs = append(fs, cell)
		}
	}
	return fs
}

func (g *Grid) UniqueRectangleWXYZWing() (used bool) {
	used = g.UniqueRectangle(g.handleURWXYZWing)
	return
}

func (g *Grid) handleURWXYZWing(rowNum1 int, pair []int, rowNum2 int) (used bool) {
	cells := make([]*Cell, 4)
	cells[0] = g.rows[rowNum1].cells[pair[0]]
	cells[1] = g.rows[rowNum1].cells[pair[1]]
	cells[2] = g.rows[rowNum2].cells[pair[0]]
	cells[3] = g.rows[rowNum2].cells[pair[1]]

	cands := cells[0].cands

	pCells := make([]*Cell, 0, 2)
	if cells[1].cands == cands {
		pCells = append(pCells, cells[2])
		pCells = append(pCells, cells[3])
	} else if cells[2].cands == cands {
		pCells = append(pCells, cells[1])
		pCells = append(pCells, cells[3])
	} else {
		return
	}

	pivotCands := pCells[0].cands.Union(pCells[1].cands).Diff(cands)
	if pivotCands.Count() != 3 && pivotCands.Count() != 4 {
		return
	}

	ok, z, wings := g.verifyURWXYZWing(cands, pCells)
	//fmt.Println(ok, z, wings)

	if !ok {
		return
	}
	sname := "Unique Rectangle WXYZ-Wing"
	if g.clearupURXYZWing(cands, z, pCells, wings) {
		used = true
		log.Printf("r%v%vc%v%v %v wr%vc%v wr%vc%v wr%vc%v %v %v",
			rowNum1, rowNum2, pair[0], pair[1], cands.ValueString(),
			wings[0].rowNum, wings[0].colNum,
			wings[1].rowNum, wings[1].colNum,
			wings[2].rowNum, wings[2].colNum,
			toValue(z), sname)
	}
	return
}

func (g *Grid) verifyURWXYZWing(urCands set.Set, pCells []*Cell) (ok bool, cand int, wings []*Cell) {

	seen0 := g.seenCells(pCells[0])
	seen0 = filterBiCands(seen0, 3)
	seen0 = filterCells(seen0, pCells[1])

	seen1 := g.seenCells(pCells[1])
	seen1 = filterBiCands(seen1, 3)
	seen1 = filterCells(seen1, pCells[0])

	p0Cands := pCells[0].cands.Diff(urCands)
	p1Cands := pCells[1].cands.Diff(urCands)

	for _, w12 := range combine(seen0, 2) {
		for _, w3 := range seen1 {
			if sameHouse(append(pCells, append(w12, w3)...)) {
				continue
			}
			ok, cand = verifyURWXYZWingCells(p0Cands, p1Cands, pCells, w12, w3)
			if ok {
				wings = append(w12, w3)
				return
			}
		}
	}

	for _, w12 := range combine(seen1, 2) {
		for _, w3 := range seen0 {
			if sameHouse(append(pCells, append(w12, w3)...)) {
				continue
			}
			ok, cand = verifyURWXYZWingCells(p0Cands, p1Cands,
				[]*Cell{pCells[1], pCells[0]}, w12, w3)

			if ok {
				wings = append(w12, w3)
				return
			}
		}
	}

	return
}

func verifyURWXYZWingCells(p0Cands, p1Cands set.Set,
	pCells, w12 []*Cell, w3 *Cell) (ok bool, cand int) {
	wz := w3.cands
	if wz.Count() != 2 {
		return
	}

	w1, w2 := w12[0], w12[1]
	xyz := w1.cands.Union(w2.cands)
	if xyz.Count() != 3 {
		return
	}

	z := xyz.Intersect(wz)
	if z.Count() != 1 {
		return
	}

	wxyz := wz.Union(xyz)
	if wxyz.Count() != 4 {
		return
	}

	pCands := p0Cands.Union(p1Cands)
	if pCands != wxyz && pCands != wxyz.Diff(z) {
		return
	}

	w := wz.Diff(z)
	if p1Cands.Intersect(w) != w {
		return
	}

	if p0Cands.Intersect(w) == w && !sameHouse([]*Cell{pCells[0], w3}) {
		return
	}

	xy := xyz.Diff(z)
	if p0Cands.Intersect(xy) != xy {
		return
	}
	if p1Cands.Intersect(xy).Count() != 0 && !sameHouse(append(w12, pCells[0])) {
		return
	}

	ok = true
	cand = z.GetList()[0]
	return
}
